COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	tree[f82,jmc]		Another scheme for using trees instead of a-lists
C00005 ENDMK
C⊗;
tree[f82,jmc]		Another scheme for using trees instead of a-lists

	This one (unlike those discussed in BALANCE[F81,JMC]) does not
try to keep the tree balanced but relies on statistics.  We hash
the variable name and use the bits of the hash to regulate branching.
Thus to find a whether a symbol is in the table, one hashes it and
branches down the tree in accordance with the hash.  As soon as
there is a unique symbol, the branching stops.

	Inserting an element in the tree again involves following
the branching until either

	a. The desired element lies in a direction where there is no
other element of the tree.  In this case we put in a pointer to the
word being inserted.

	b. We reach a word which shares all bits so far with the word
being inserted.  In this case  we build branches until the two words
diverge.

	In this second case, it can happen that two words will share
bits for some distance.  In fact, on the average, they'll share it for
two levels.

	This scheme would be especially economical of space if the items
were large compared to the length of the tree leading to them.  It looks
like the system will be economical if the items are two or three words
of unshared structure beyond the symbol itself.

At the moment, 1982 Oct 9, the whole idea doesn't seem coherent, because
it doesn't provide for the stack-like aspect of the a-list.